package acm.蓝桥12;

import java.util.Arrays;
import java.util.Scanner;

//dfs
public class I吃巧克力 {
    static int maxN = 100001;
    static int maxM = 100001;
    static int[][] arr = new int[maxM][3];
    static int n, m; //m天数，n种类

    /**
     * 先按天数排个序，在dfs吃不吃
     * @param args
     */
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        m = sc.nextInt();
        n = sc.nextInt();
        for (int i = 0; i < n; i++) {
            arr[i][0] = sc.nextInt();
            arr[i][1] = sc.nextInt();
            arr[i][2] = sc.nextInt();
        }
        Arrays.sort(arr, 0, n, (a, b) -> a[1] - b[1]);  //按天数排序
//        long dfs = dfs(1, 0);
//        if (dfs==Integer.MAX_VALUE){
//            System.out.println(-1);
//            return;
//        }
        long dfs = dpFun();
        System.out.println(dfs);
    }

    /**
     * 在天数为d时，有i+种可选
     */
    public static long dfs(int d, int i) {
//        if (dp[d][i]!=-2){
//            return dp[d][i];
//        }
        if (d == m + 1) {    //已经过了最后一天
            return 0;
        }
        if (i == n) { //没有可选
            return -1;
        }
        if (arr[i][1] < d) {   //过了保质期
            return dfs(d, i + 1);
        }
        long res = Integer.MAX_VALUE;
        long count = Math.min(arr[i][1] - d + 1, arr[i][2]);   //未过期的有多少
        for (int l = 0; l <= count; l++) {
            long dfs = dfs(d + l, i + 1);
            if (dfs != -1) {
                dfs = dfs + (long) l * arr[i][0];
                res = Math.min(res, dfs);
            }
        }
        return res;
    }

    /**
     * 表示：dp[i][j]：在第i天，有j种巧克力可选时，最少花费
     *      可选操作：
     *          吃0个j种巧克力。dp[i][j]=dp[i][j-1]
     *          吃1个....,dp[i][j]=dp[i-1][j-1]+arr[j][0]
     *          吃k个，dp[i][j]=dp[i-k][j-1]+k*arr[j][0]   ,k+d<=arr[j][1]&&k<=arr[j][2]
     *       边界：
     *          dp[1..n][0]=-1
     *          dp[0][0...n]=0
     *
     *
     * @return
     */
    public static long dpFun() {
        int[] dp = new int[m + 1];
        Arrays.fill(dp, Integer.MAX_VALUE);
        dp[0] = 0;
        for (int j = 1; j <= n; j++) {
            for (int i = 1; i <= m; i++) {
                if (arr[j - 1][1] < i) {
                    continue;
                }
                dp[i]=Math.min(dp[i-1]+arr[j-1][0],dp[i]);

            }
        }
        return dp[m];
    }
}
